import pandas as pd
import numpy as np
import math
import matplotlib.pyplot as plt
from scipy.spatial.kdtree import KDTree
from sklearn.cluster import DBSCAN

def readDataSet(filename, div=2):
    data = np.loadtxt(filename)
    return data

def readDataSetwithLabel(filename, div=2):
    matrix = np.loadtxt(filename)
    label = matrix[:, -1]
    matrix = np.delete(matrix, -1, axis=1)
    return matrix, label

def readLabel(filename):
    data = pd.read_csv(filename, header=None)
    matrix = np.array(data)
    return matrix

def getKNN(matrix, k):
    '''
    获得knn连接图
    :param matrix:  坐标信息
    :param k: k个最近邻
    :return: dd: 距离矩阵，最近的k个点的距离
    :return: ii: 索引矩阵，最近的k个点的索引
    '''
    kd_tree = KDTree(matrix)
    dd, ii = kd_tree.query(matrix, k = k+1)
    dd = np.delete(dd, 0, axis=1)
    ii = np.delete(ii, 0, axis=1)
    return dd, ii

def get_density(dd):
    length = dd.shape[0]
    k = dd.shape[1]
    denstity = np.zeros((length, k), dtype=float)
    k_density = np.zeros((length, 1), dtype=float)
    for i in range(length):
        for j in range(k):
            if j == 0:
                denstity[i][j] = dd[i][j]
            else:
                denstity[i][j] = denstity[i][j-1] + dd[i][j]
        k_density[i] = denstity[i][k-1]
    return denstity, k_density

def ExpandCluster(sorted_ind, ind, ii, cluster_id, denstiy, k_density, minpts, result):
    initial = sorted_ind[ind][0]
    k = ii.shape[1]
    begin = 0
    end = 0
    seeds = []
    seeds.append(initial)
    end = end + 1
    for i in range(k):
        seeds.append(ii[initial][i])
        end = end + 1
    if denstiy[initial][minpts-1] > k_density[initial][0]:
        # 这是一个噪声点
        result[sorted_ind[initial]] = -1
        return False
    else:
        for i in seeds:
            result[i] = cluster_id
        begin = begin + 1
        while begin < end:
            currentP = seeds[begin]
            if denstiy[currentP][minpts-1] <= k_density[initial][0]:
                for j in range(k):
                    if denstiy[currentP][j] > k_density[initial]:
                        break
                    resultP = ii[currentP][j]
                    if result[resultP] == 0 or result[resultP] == -1:
                        if result[resultP] == 0:
                            seeds.append(resultP)
                            end = end + 1
                        result[resultP] = cluster_id
            begin = begin + 1
        return True

def cmdd(matrix, minpts, k):
    length = matrix.shape[0]
    dd, ii =getKNN(matrix, k)
    density, k_density = get_density(dd)
    sorted_ind = k_density.reshape((1, length)).argsort().reshape((length, 1))
    result = np.zeros((length, 1), dtype=int)
    cluster_id = 1
    for i in range(length):
        if result[sorted_ind[i]] == 0:
            if ExpandCluster(sorted_ind, i, ii, cluster_id, density, k_density, minpts, result):
                cluster_id = cluster_id + 1
    return result

def plotResult(location, result, filename):
    length = len(result)
    markers = ['.', '*', '+', 'x', '^']
    colors = ['maroon', 'red', 'peru', 'gold', 'olive', 'yellowgreen', 'lawngreen', 'springgreen']
    colors = colors + ['turquoise', 'teal', 'deepskyblue', 'dodgerblue', 'royalblue', 'navy']
    colors = colors + ['slategrey', 'orchid', 'm', 'deeppink', 'crimson']
    plt.figure(figsize=(10, 10))

    title = "CMDD Clustering Result"
    plt.title(title)
    for i in range(0, length):
        index = int(result[i])
        if index == -1:
            plt.plot(location[i][0], location[i][1], color=(0,0,0),  marker='.')
        else:
            plt.plot(location[i][0], location[i][1], color=colors[index%19], marker=markers[index%5])
    plt.xlabel('Attribute 1'), plt.ylabel('Attribute 2')

    plt.savefig(filename)
    plt.show()

if __name__ == '__main__':
    k = 13
    minpts = 4
    input_file = 'Jain.txt'
    output_file = 'result.txt'
    output_img = 'result.png'
    is_with_label = 1
    dim = 2
    matrix, label = readDataSetwithLabel(input_file, dim)
    result = cmdd(matrix, minpts, k)
    plotResult(matrix, result, output_img)
    np.savetxt(output_file, result)

